package interview.huawei.tjt.training.huisu;

import java.util.*;

/**
 * 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
 *
 * 提示：
 *
 * 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
 * 所有的机场都用三个大写字母表示（机场代码）。
 * 假定所有机票至少存在一种合理的行程。
 * 所有的机票必须都用一次 且 只能用一次。
 * 示例 1：
 *
 * 输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
 * 输出：["JFK", "MUC", "LHR", "SFO", "SJC"]
 * 示例 2：
 *
 * 输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
 */
public class FindItinerary {

    private static LinkedList<String> result = new LinkedList<>();
    private static Map<String, Map<String, Integer>> map = new HashMap<>();  // map<出发机场, map<到达机场, 航班次数>>
    private static boolean[] used;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    }

    private static List<String> findItinerary (List<List<String>> tickets) {
        for (List<String> t : tickets) {  // t.get(0):表示出发机场的名称  t.get(1)：表示到达机场的名称
            Map<String, Integer> temp; // map<到达机场, 航班次数>
            // 判断Map中有没有当前机票的出发站
            if (map.containsKey(t.get(0))) {  // 包含的情况
                temp = map.get(t.get(0)); // temp里面存放的是<到达机场, 航班次数>
                // temp.getOrDefault(t.get(1), 0) : 判断当前temp里面有没有当前机票的到达机场，有的话就返回到达机场的航班次数，没有的话就将到达该机场的航班次数设为0
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {  //
                temp = new TreeMap<>(); // 升序Map
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);
        }
        result.add("JFK");
        helper(tickets.size());
        return result;
    }

    private static boolean helper (int ticketNum) {
        // 终止条件
        if (result.size() == ticketNum + 1) {
            return true;
        }

        String last = result.getLast();
        if (map.containsKey(last)) {  // 防止出现null
            for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
                int count = target.getValue();
                if (count > 0) {
                    result.add(target.getKey());
                    target.setValue(count - 1);
                    if (helper(ticketNum)) {
                        return true;
                    }
                    result.removeLast();
                    target.setValue(count);
                }
            }
        }

        return false;
    }

}
